package com.demo.java.OD601_650.OD628;

import java.util.Scanner;
import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【计算快递业务主站点(A卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146886109
 */
public class OdMain {
    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);
        int N = in.nextInt(); // 站点数量

        int[][] matrix = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = in.nextInt(); // 读取邻接矩阵
            }
        }

        // 记录已经连接的站点
        Set<Integer> site_set = new HashSet<>();
        // 记录需要的最小站点数
        int res = 0;

        // 遍历所有站点，检查每个站点是否已经连接过
        for (int i = 0; i < N; i++) {
            // 如果站点已经在集合中，跳过
            if (site_set.contains(i)) {
                continue;
            }
            // 使用临时集合记录当前联通的站点
            Set<Integer> temp = new HashSet<>();
            temp.add(i); // 当前站点已经访问
            // 查找该站点所属的联通分量
            check(temp, i, matrix);
            // 将所有联通分量的站点添加到已访问集合中
            site_set.addAll(temp);
            // 每发现一个新的联通分量，站点数增加1
            res++;
        }

        // 输出最小站点数
        System.out.println(res);
    }

    // 深度优先搜索（DFS），找出联通分量
    public static void check(Set<Integer> site_set, int n, int[][] matrix) {
        // 遍历所有站点，查找与当前站点n相连的站点
        for (int i = 0; i < matrix.length; i++) {
            // 如果当前站点已经在集合中，跳过
            if (site_set.contains(i)) {
                continue;
            }
            // 如果当前站点和n相连，加入集合
            if (n != i && matrix[n][i] == 1) {
                site_set.add(i);
                // 继续查找与i相连的站点
                check(site_set, i, matrix);
            }
        }
    }
}